﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;

namespace RegexParser
{
	/// <summary>
	/// Defines the parsing behavior necessary to parse and tokenize a regular expression.
	/// </summary>
	public class Parser
	{
		public enum HintType
		{
			Grouping = 1,
			NamedCharacterClass = 2,
			CharacterClass = 3,
			Character = 4,
			Quantifier = 5
		}

		private Dictionary<HintType, List<Hint>> _RegexHints;
		public Dictionary<HintType, List<Hint>> RegexHints
		{
			get
			{
				if (_RegexHints == null)
				{
					_RegexHints = new Dictionary<HintType, List<Hint>>();

					var RegexGroupings = new List<Hint>();
					RegexGroupings.Add(new Hint("(pattern)", "(__)", "Captures the specified pattern as a group. Each group is numbered automatically starting from 1. Group 0 is actually not a group at all but refers to the text matched by the entire regular expression."));
					RegexGroupings.Add(new Hint("(?<name>pattern)", "(?<__>__)", "Captures the specified pattern into the specified group name. The string used for the name must not contain any punctuation and cannot begin with a number."));
					RegexGroupings.Add(new Hint("(?<name1-name2>pattern)", "(?<__-__>__)", "Defines a balancing group definition."));
					RegexGroupings.Add(new Hint("(?:pattern)", "(?:__)", "Does not capture the substring matched by this pattern. Known as a noncapturing group."));
					RegexGroupings.Add(new Hint("(?=pattern)", "(?=__)", "Asserts that the specified pattern exists immediately after this location. Known as a positive lookahead."));
					RegexGroupings.Add(new Hint("(?!pattern)", "(?!__)", "Asserts that the specified pattern does not exist immediately after this location. Known as a negative lookahead."));
					RegexGroupings.Add(new Hint("(?<=pattern)", "(?<=__)", "Asserts that the specified pattern exists immediately before this location. Known as a positive lookbehind."));
					RegexGroupings.Add(new Hint("(?<!pattern)", "(?<!__)", "Asserts that the specified pattern does not exist immediately before this location. Known as a negative lookbehind."));
					RegexGroupings.Add(new Hint("(?imnsx-imnsx)", "(?__)", "Applies or disables the specified options."));
					RegexGroupings.Add(new Hint("(?imnsx-imnsx:pattern)", "(?__:__)", "Applies or disables the specified options within subexpression."));
					RegexGroupings.Add(new Hint("(?>pattern)", "(?>__)", @"Nonbacktracking (or greedy) subexpression.  Also known as an atomic group."));
					RegexGroupings.Add(new Hint("(?(pattern)yes|no)", "(?(__)__|__)", "Matches the first pattern in the OR statement (yes) if the specified pattern is found at this point. Otherwise, matches the second pattern in the OR statement (no)."));
					RegexGroupings.Add(new Hint("(?(<name>)yes|no)", "(?(<__>)__|__)", "Matches the first pattern in the OR statement (yes) if the specified named group is found at this point. Otherwise, matches the second pattern in the OR statement (no)."));
					RegexGroupings.Add(new Hint("(?#comment)", "(?#__)", "Everything from the pound sign (#) to the end parenthesis is a comment and will be ignored."));
					_RegexHints.Add(HintType.Grouping, RegexGroupings);

					var RegexCharacterClasses = new List<Hint>();
					RegexCharacterClasses.Add(new Hint("[abc]", "[__]", "A bracket expression (may contain more than one character). Matches any character that is contained within the brackets, in no particular order."));
					RegexCharacterClasses.Add(new Hint("[^abc]", "[^__]", "The opposite of [ ]. Matches all characters not contained within the brackets."));
					RegexCharacterClasses.Add(new Hint("[a-z]", "[__-__]", "Character range: Matches any single character in the range from first to last."));
					_RegexHints.Add(HintType.CharacterClass, RegexCharacterClasses);

					var RegexQuantifiers = new List<Hint>();
					RegexQuantifiers.Add(new Hint("{n}", "{__}", "Repeat exactly n times."));
					RegexQuantifiers.Add(new Hint("{n,}", "{__,}", "Repeat at least n times, matching as many times as possible."));
					RegexQuantifiers.Add(new Hint("{n,}?", "{__,}?", "Repeat at least n times, matching as few times as possible."));
					RegexQuantifiers.Add(new Hint("{n,m}", "{__,__}", "Repeat at least n times, but no more than m times."));
					RegexQuantifiers.Add(new Hint("{n,m}?", "{__,__}?", "Repeat at least n times, but no more than m times while matching as few as possible."));
					_RegexHints.Add(HintType.Quantifier, RegexQuantifiers);

					var RegexCharacters = new List<Hint>();
					RegexCharacters.Add(new Hint(@"\", @"\", @"Escape character. In front of any of the special characters (. $ ^ { [ ( | ) * + ? \), this will match the character itself."));
					RegexCharacters.Add(new Hint(@"\w", @"\w", @"Matches an alpha-numeric character (a-z, A-Z, 0-9, and underscore).", "an alpha-numeric character (a-z, A-Z, 0-9, and underscore)"));
					RegexCharacters.Add(new Hint(@"\W", @"\W", @"The opposite of \w. Matches any non-alphanumeric character.", "a non-alphanumeric character"));
					RegexCharacters.Add(new Hint(@"\d", @"\d", @"Matches a decimal character (0-9).", "a decimal character (0-9)"));
					RegexCharacters.Add(new Hint(@"\D", @"\D", @"The opposite of \d. Matches any non-decimal character.", "a non-decimal character"));
					RegexCharacters.Add(new Hint(@"\s", @"\s", @"Matches a character of whitespace (space, tab, carriage return, line feed).", "a character of whitespace (space, tab, carriage return, line feed)"));
					RegexCharacters.Add(new Hint(@"\S", @"\S", @"The opposite of \s. Matches any non-whitespace character.", "a non-whitespace character"));
					RegexCharacters.Add(new Hint(@"\r", @"\r", @"Matches a carriage return.", "a carriage return"));
					RegexCharacters.Add(new Hint(@"\n", @"\n", @"Matches a new line (line feed).", "a new line (line feed)"));
					RegexCharacters.Add(new Hint(@"\f", @"\f", @"Matches a form feed.", "a form feed"));
					RegexCharacters.Add(new Hint(@"\t", @"\t", @"Matches a tab.", "a tab"));
					RegexCharacters.Add(new Hint(@"\v", @"\v", @"Matches a vertical tab.", "a tab"));
					RegexCharacters.Add(new Hint(@"\a", @"\a", @"Matches a bell character.", "a bell character"));
					RegexCharacters.Add(new Hint(@"\e", @"\e", @"Matches an escape.", "an escape"));
					RegexCharacters.Add(new Hint(@"\A", @"\A", @"The match must occur at the start of the string."));
					RegexCharacters.Add(new Hint(@"\Z", @"\Z", @"The match must occur at the end of the string or before \n at the end of the string."));
					RegexCharacters.Add(new Hint(@"\z", @"\z", @"The match must occur at the end of the string."));
					RegexCharacters.Add(new Hint(@"\G", @"\G", @"The match must occur at the point where the previous match ended."));
					RegexCharacters.Add(new Hint(@"\b", @"\b", @"Asserts a boundary between word and non-word characters.  Or in a character class, matches a backspace.", "a backspace"));
					RegexCharacters.Add(new Hint(@"\B", @"\B", @"The opposite of \b. Asserts a location that is not a boundary between word and non-word characters."));
					RegexCharacters.Add(new Hint(@"\p{name}", @"\p", @"Matches any single character in the Unicode general category or named block specified by name."));
					RegexCharacters.Add(new Hint(@"\P{name}", @"\P", @"Matches any single character that is not in the Unicode general category or named block specified by name."));
					_RegexHints.Add(HintType.Character, RegexCharacters);

					var NamedCharacterClasses = new List<Hint>();
					NamedCharacterClasses.Add(new Hint("{Lu}", "Letter, Uppercase"));
					NamedCharacterClasses.Add(new Hint("{Ll}", "Letter, Lowercase"));
					NamedCharacterClasses.Add(new Hint("{Lt}", "Letter, Titlecase"));
					NamedCharacterClasses.Add(new Hint("{Lm}", "Letter, Modifier"));
					NamedCharacterClasses.Add(new Hint("{Lo}", "Letter, Other"));
					NamedCharacterClasses.Add(new Hint("{L}", "All letter characters. This includes the Lu, Ll, Lt, Lm, and Lo characters."));
					NamedCharacterClasses.Add(new Hint("{Mn}", "Mark, Nonspacing"));
					NamedCharacterClasses.Add(new Hint("{Mc}", "Mark, Spacing Combining"));
					NamedCharacterClasses.Add(new Hint("{Me}", "Mark, Enclosing"));
					NamedCharacterClasses.Add(new Hint("{M}", "All diacritic marks. This includes the Mn, Mc, and Me categories."));
					NamedCharacterClasses.Add(new Hint("{Nd}", "Number, Decimal Digit"));
					NamedCharacterClasses.Add(new Hint("{Nl}", "Number, Letter"));
					NamedCharacterClasses.Add(new Hint("{No}", "Number, Other"));
					NamedCharacterClasses.Add(new Hint("{N}", "All numbers. This includes the Nd, Nl, and No categories."));
					NamedCharacterClasses.Add(new Hint("{Pc}", "Punctuation, Connector"));
					NamedCharacterClasses.Add(new Hint("{Pd}", "Punctuation, Dash"));
					NamedCharacterClasses.Add(new Hint("{Ps}", "Punctuation, Open"));
					NamedCharacterClasses.Add(new Hint("{Pe}", "Punctuation, Close"));
					NamedCharacterClasses.Add(new Hint("{Pi}", "Punctuation, Initial quote (may behave like Ps or Pe depending on usage)"));
					NamedCharacterClasses.Add(new Hint("{Pf}", "Punctuation, Final quote (may behave like Ps or Pe depending on usage)"));
					NamedCharacterClasses.Add(new Hint("{Po}", "Punctuation, Other"));
					NamedCharacterClasses.Add(new Hint("{P}", "All punctuation characters. This includes the Pc, Pd, Ps, Pe, Pi, Pf, and Po categories."));
					NamedCharacterClasses.Add(new Hint("{Sm}", "Symbol, Math"));
					NamedCharacterClasses.Add(new Hint("{Sc}", "Symbol, Currency"));
					NamedCharacterClasses.Add(new Hint("{Sk}", "Symbol, Modifier"));
					NamedCharacterClasses.Add(new Hint("{So}", "Symbol, Other"));
					NamedCharacterClasses.Add(new Hint("{S}", "All symbols. This includes the Sm, Sc, Sk, and So categories."));
					NamedCharacterClasses.Add(new Hint("{Zs}", "Separator, Space"));
					NamedCharacterClasses.Add(new Hint("{Zl}", "Separator, Line"));
					NamedCharacterClasses.Add(new Hint("{Zp}", "Separator, Paragraph"));
					NamedCharacterClasses.Add(new Hint("{Z}", "All separator characters. This includes the Zs, Zl, and Zp categories."));
					NamedCharacterClasses.Add(new Hint("{Cc}", "Other, Control"));
					NamedCharacterClasses.Add(new Hint("{Cf}", "Other, Format"));
					NamedCharacterClasses.Add(new Hint("{Cs}", "Other, Surrogate"));
					NamedCharacterClasses.Add(new Hint("{Co}", "Other, Private Use"));
					NamedCharacterClasses.Add(new Hint("{Cn}", "Other, Not Assigned (no characters have this property)"));
					NamedCharacterClasses.Add(new Hint("{C}", "All control characters. This includes the Cc, Cf, Cs, Co, and Cn categories."));
					NamedCharacterClasses.Add(new Hint("{IsBasicLatin}", "0000 - 007F"));
					NamedCharacterClasses.Add(new Hint("{IsLatin-1Supplement}", "0080 - 00FF"));
					NamedCharacterClasses.Add(new Hint("{IsLatinExtended-A}", "0100 - 017F"));
					NamedCharacterClasses.Add(new Hint("{IsLatinExtended-B}", "0180 - 024F"));
					NamedCharacterClasses.Add(new Hint("{IsIPAExtensions}", "0250 - 02AF"));
					NamedCharacterClasses.Add(new Hint("{IsSpacingModifierLetters}", "02B0 - 02FF"));
					NamedCharacterClasses.Add(new Hint("{IsCombiningDiacriticalMarks}", "0300 - 036F"));
					NamedCharacterClasses.Add(new Hint("{IsGreek}", "0370 - 03FF"));
					NamedCharacterClasses.Add(new Hint("{IsGreekandCoptic}", "0370 - 03FF"));
					NamedCharacterClasses.Add(new Hint("{IsCyrillic}", "0400 - 04FF"));
					NamedCharacterClasses.Add(new Hint("{IsCyrillicSupplement}", "0500 - 052F"));
					NamedCharacterClasses.Add(new Hint("{IsArmenian}", "0530 - 058F"));
					NamedCharacterClasses.Add(new Hint("{IsHebrew}", "0590 - 05FF"));
					NamedCharacterClasses.Add(new Hint("{IsArabic}", "0600 - 06FF"));
					NamedCharacterClasses.Add(new Hint("{IsSyriac}", "0700 - 074F"));
					NamedCharacterClasses.Add(new Hint("{IsThaana}", "0780 - 07BF"));
					NamedCharacterClasses.Add(new Hint("{IsDevanagari}", "0900 - 097F"));
					NamedCharacterClasses.Add(new Hint("{IsBengali}", "0980 - 09FF"));
					NamedCharacterClasses.Add(new Hint("{IsGurmukhi}", "0A00 - 0A7F"));
					NamedCharacterClasses.Add(new Hint("{IsGujarati}", "0A80 - 0AFF"));
					NamedCharacterClasses.Add(new Hint("{IsOriya}", "0B00 - 0B7F"));
					NamedCharacterClasses.Add(new Hint("{IsTamil}", "0B80 - 0BFF"));
					NamedCharacterClasses.Add(new Hint("{IsTelugu}", "0C00 - 0C7F"));
					NamedCharacterClasses.Add(new Hint("{IsKannada}", "0C80 - 0CFF"));
					NamedCharacterClasses.Add(new Hint("{IsMalayalam}", "0D00 - 0D7F"));
					NamedCharacterClasses.Add(new Hint("{IsSinhala}", "0D80 - 0DFF"));
					NamedCharacterClasses.Add(new Hint("{IsThai}", "0E00 - 0E7F"));
					NamedCharacterClasses.Add(new Hint("{IsLao}", "0E80 - 0EFF"));
					NamedCharacterClasses.Add(new Hint("{IsTibetan}", "0F00 - 0FFF"));
					NamedCharacterClasses.Add(new Hint("{IsMyanmar}", "1000 - 109F"));
					NamedCharacterClasses.Add(new Hint("{IsGeorgian}", "10A0 - 10FF"));
					NamedCharacterClasses.Add(new Hint("{IsHangulJamo}", "1100 - 11FF"));
					NamedCharacterClasses.Add(new Hint("{IsEthiopic}", "1200 - 137F"));
					NamedCharacterClasses.Add(new Hint("{IsCherokee}", "13A0 - 13FF"));
					NamedCharacterClasses.Add(new Hint("{IsUnifiedCanadianAboriginalSyllabics}", "1400 - 167F"));
					NamedCharacterClasses.Add(new Hint("{IsOgham}", "1680 - 169F"));
					NamedCharacterClasses.Add(new Hint("{IsRunic}", "16A0 - 16FF"));
					NamedCharacterClasses.Add(new Hint("{IsTagalog}", "1700 - 171F"));
					NamedCharacterClasses.Add(new Hint("{IsHanunoo}", "1720 - 173F"));
					NamedCharacterClasses.Add(new Hint("{IsBuhid}", "1740 - 175F"));
					NamedCharacterClasses.Add(new Hint("{IsTagbanwa}", "1760 - 177F"));
					NamedCharacterClasses.Add(new Hint("{IsKhmer}", "1780 - 17FF"));
					NamedCharacterClasses.Add(new Hint("{IsMongolian}", "1800 - 18AF"));
					NamedCharacterClasses.Add(new Hint("{IsLimbu}", "1900 - 194F"));
					NamedCharacterClasses.Add(new Hint("{IsTaiLe}", "1950 - 197F"));
					NamedCharacterClasses.Add(new Hint("{IsKhmerSymbols}", "19E0 - 19FF"));
					NamedCharacterClasses.Add(new Hint("{IsPhoneticExtensions}", "1D00 - 1D7F"));
					NamedCharacterClasses.Add(new Hint("{IsLatinExtendedAdditional}", "1E00 - 1EFF"));
					NamedCharacterClasses.Add(new Hint("{IsGreekExtended}", "1F00 - 1FFF"));
					NamedCharacterClasses.Add(new Hint("{IsGeneralPunctuation}", "2000 - 206F"));
					NamedCharacterClasses.Add(new Hint("{IsSuperscriptsandSubscripts}", "2070 - 209F"));
					NamedCharacterClasses.Add(new Hint("{IsCurrencySymbols}", "20A0 - 20CF"));
					NamedCharacterClasses.Add(new Hint("{IsCombiningDiacriticalMarksforSymbols}", "20D0 - 20FF"));
					NamedCharacterClasses.Add(new Hint("{IsCombiningMarksforSymbols}", "20D0 - 20FF"));
					NamedCharacterClasses.Add(new Hint("{IsLetterlikeSymbols}", "2100 - 214F"));
					NamedCharacterClasses.Add(new Hint("{IsNumberForms}", "2150 - 218F"));
					NamedCharacterClasses.Add(new Hint("{IsArrows}", "2190 - 21FF"));
					NamedCharacterClasses.Add(new Hint("{IsMathematicalOperators}", "2200 - 22FF"));
					NamedCharacterClasses.Add(new Hint("{IsMiscellaneousTechnical}", "2300 - 23FF"));
					NamedCharacterClasses.Add(new Hint("{IsControlPictures}", "2400 - 243F"));
					NamedCharacterClasses.Add(new Hint("{IsOpticalCharacterRecognition}", "2440 - 245F"));
					NamedCharacterClasses.Add(new Hint("{IsEnclosedAlphanumerics}", "2460 - 24FF"));
					NamedCharacterClasses.Add(new Hint("{IsBoxDrawing}", "2500 - 257F"));
					NamedCharacterClasses.Add(new Hint("{IsBlockElements}", "2580 - 259F"));
					NamedCharacterClasses.Add(new Hint("{IsGeometricShapes}", "25A0 - 25FF"));
					NamedCharacterClasses.Add(new Hint("{IsMiscellaneousSymbols}", "2600 - 26FF"));
					NamedCharacterClasses.Add(new Hint("{IsDingbats}", "2700 - 27BF"));
					NamedCharacterClasses.Add(new Hint("{IsMiscellaneousMathematicalSymbols-A}", "27C0 - 27EF"));
					NamedCharacterClasses.Add(new Hint("{IsSupplementalArrows-A}", "27F0 - 27FF"));
					NamedCharacterClasses.Add(new Hint("{IsBraillePatterns}", "2800 - 28FF"));
					NamedCharacterClasses.Add(new Hint("{IsSupplementalArrows-B}", "2900 - 297F"));
					NamedCharacterClasses.Add(new Hint("{IsMiscellaneousMathematicalSymbols-B}", "2980 - 29FF"));
					NamedCharacterClasses.Add(new Hint("{IsSupplementalMathematicalOperators}", "2A00 - 2AFF"));
					NamedCharacterClasses.Add(new Hint("{IsMiscellaneousSymbolsandArrows}", "2B00 - 2BFF"));
					NamedCharacterClasses.Add(new Hint("{IsCJKRadicalsSupplement}", "2E80 - 2EFF"));
					NamedCharacterClasses.Add(new Hint("{IsKangxiRadicals}", "2F00 - 2FDF"));
					NamedCharacterClasses.Add(new Hint("{IsIdeographicDescriptionCharacters}", "2FF0 - 2FFF"));
					NamedCharacterClasses.Add(new Hint("{IsCJKSymbolsandPunctuation}", "3000 - 303F"));
					NamedCharacterClasses.Add(new Hint("{IsHiragana}", "3040 - 309F"));
					NamedCharacterClasses.Add(new Hint("{IsKatakana}", "30A0 - 30FF"));
					NamedCharacterClasses.Add(new Hint("{IsBopomofo}", "3100 - 312F"));
					NamedCharacterClasses.Add(new Hint("{IsHangulCompatibilityJamo}", "3130 - 318F"));
					NamedCharacterClasses.Add(new Hint("{IsKanbun}", "3190 - 319F"));
					NamedCharacterClasses.Add(new Hint("{IsBopomofoExtended}", "31A0 - 31BF"));
					NamedCharacterClasses.Add(new Hint("{IsKatakanaPhoneticExtensions}", "31F0 - 31FF"));
					NamedCharacterClasses.Add(new Hint("{IsEnclosedCJKLettersandMonths}", "3200 - 32FF"));
					NamedCharacterClasses.Add(new Hint("{IsCJKCompatibility}", "3300 - 33FF"));
					NamedCharacterClasses.Add(new Hint("{IsCJKUnifiedIdeographsExtensionA}", "3400 - 4DBF"));
					NamedCharacterClasses.Add(new Hint("{IsYijingHexagramSymbols}", "4DC0 - 4DFF"));
					NamedCharacterClasses.Add(new Hint("{IsCJKUnifiedIdeographs}", "4E00 - 9FFF"));
					NamedCharacterClasses.Add(new Hint("{IsYiSyllables}", "A000 - A48F"));
					NamedCharacterClasses.Add(new Hint("{IsYiRadicals}", "A490 - A4CF"));
					NamedCharacterClasses.Add(new Hint("{IsHangulSyllables}", "AC00 - D7AF"));
					NamedCharacterClasses.Add(new Hint("{IsHighSurrogates}", "D800 - DB7F"));
					NamedCharacterClasses.Add(new Hint("{IsHighPrivateUseSurrogates}", "DB80 - DBFF"));
					NamedCharacterClasses.Add(new Hint("{IsLowSurrogates}", "DC00 - DFFF"));
					NamedCharacterClasses.Add(new Hint("{IsPrivateUse}", "E000 - F8FF"));
					NamedCharacterClasses.Add(new Hint("{IsPrivateUseArea}", "E000 - F8FF"));
					NamedCharacterClasses.Add(new Hint("{IsCJKCompatibilityIdeographs}", "F900 - FAFF"));
					NamedCharacterClasses.Add(new Hint("{IsAlphabeticPresentationForms}", "FB00 - FB4F"));
					NamedCharacterClasses.Add(new Hint("{IsArabicPresentationForms-A}", "FB50 - FDFF"));
					NamedCharacterClasses.Add(new Hint("{IsVariationSelectors}", "FE00 - FE0F"));
					NamedCharacterClasses.Add(new Hint("{IsCombiningHalfMarks}", "FE20 - FE2F"));
					NamedCharacterClasses.Add(new Hint("{IsCJKCompatibilityForms}", "FE30 - FE4F"));
					NamedCharacterClasses.Add(new Hint("{IsSmallFormVariants}", "FE50 - FE6F"));
					NamedCharacterClasses.Add(new Hint("{IsArabicPresentationForms-B}", "FE70 - FEFF"));
					NamedCharacterClasses.Add(new Hint("{IsHalfwidthandFullwidthForms}", "FF00 - FFEF"));
					NamedCharacterClasses.Add(new Hint("{IsSpecials}", "FFF0 - FFFF"));
					_RegexHints.Add(HintType.NamedCharacterClass, NamedCharacterClasses);
				}
				return _RegexHints;
			}
		}

		public bool IsValid;

		/// <summary>
		/// Positions of hints to be used for code completion.
		/// </summary>
		public List<KeyValuePair<int, HintType>> RegexHintPositions;

		/// <summary>
		/// A list of top-level tokens.  By using this list, you'll need to crawl the hierarchy to discover all of the tokens.
		/// </summary>
		public List<RegexToken> Tokens;

		private int ParenthesesCount;
		private int BracketsCount;
		private int Position;
		private string Pattern;
		private bool IsDirty = false;

		private List<RegexToken> _FlattenedTokens;

		/// <summary>
		/// A flattened list of tokens in order.
		/// </summary>
		public List<RegexToken> FlattenedTokens
		{
			get
			{
				if (_FlattenedTokens == null || IsDirty)
				{
					IsDirty = false;
					_FlattenedTokens = new List<RegexToken>();
					GetFlattenedTokens(Tokens);
				}
				return _FlattenedTokens;
			}
		}

		private void GetFlattenedTokens(List<RegexToken> MyTokens)
		{
			foreach (var MyToken in MyTokens)
			{
				_FlattenedTokens.Add(MyToken);

				if (!MyToken.TokensEmpty)
				{
					GetFlattenedTokens(MyToken.Tokens);
				}
			}
		}

		public RegexToken GetTokenAtPosition(int _Position)
		{
			foreach (var Token in FlattenedTokens)
			{
				if (_Position >= Token.Position && _Position <= Token.Position + Token.Pattern.Length)
					return Token;
			}
			return null;
		}

		public RegexToken GetNextToken(RegexToken _Token)
		{
			List<RegexToken> MyTokens;
			if (_Token.Parent != null)
				MyTokens = _Token.Parent.Tokens;
			else
				MyTokens = Tokens;

			int TokenIndex = MyTokens.IndexOf(_Token) + 1;

			if (TokenIndex < MyTokens.Count)
				return MyTokens[TokenIndex];
			else
				return null;
		}

		public RegexToken GetPreviousToken(RegexToken _Token)
		{
			List<RegexToken> MyTokens;
			if (_Token.Parent != null)
				MyTokens = _Token.Parent.Tokens;
			else
				MyTokens = Tokens;

			int TokenIndex = MyTokens.IndexOf(_Token) - 1;

			if (TokenIndex >= 0)
				return MyTokens[TokenIndex];
			else
				return null;
		}

		private void AddToken(int EndPosition, RegexToken.Categories Category = RegexToken.Categories.OrdinaryCharacter)
		{
			IsDirty = true;

			if (Category == RegexToken.Categories.Invalid) IsValid = false;

			var MyTokens = Tokens;
			int Depth = ParenthesesCount;

			RegexToken LastToken = null;

			while (Depth > 0)
			{
				LastToken = MyTokens.Last();
				MyTokens = LastToken.Tokens;
				Depth--;
			}

			if (LastToken == null)
				MyTokens.Add(new RegexToken(Pattern.Substring(Position, EndPosition - Position + 1), Position, Category));
			else
				MyTokens.Add(new RegexToken(LastToken, Pattern.Substring(Position, EndPosition - Position + 1), Position, Category));

			Position = EndPosition + 1;
		}

		/// <summary>
		/// Returns true if two regular expressions have any possible overlapping single-character matches in the first 1024 characters of the Unicode character set.  Otherwise, returns false.
		/// </summary>
		/// <param name="r1"></param>
		/// <param name="r2"></param>
		/// <returns></returns>
		public bool IsOverlapping(Regex r1, Regex r2)
		{
			for (int i = 0; i < 1024; i++)
			{
				string text = ((char)i).ToString();
				if (r1.IsMatch(text))
				{
					if (r2.IsMatch(text))
					{
						return true;
					}
				}
			}

			return false;
		}

		/// <summary>
		/// Run the RegexParser against the specified Pattern to obtain a tree of Tokens.
		/// </summary>
		/// <param name="Pattern"></param>
		public void Run(string pattern, bool ignorePatternWhitespace = false)
		{
			IsDirty = true;
			IsValid = true;

			ParenthesesCount = 0;
			BracketsCount = 0;
			Pattern = pattern;
			Position = 0;

			Tokens = new List<RegexToken>();
			RegexHintPositions = new List<KeyValuePair<int, HintType>>();

			bool InsideInlineComment = false;
			bool InsideComment = false;

			for (int i = 0; i < Pattern.Length; i++)
			{
				if (InsideInlineComment)
				{
					if (Pattern[i] == '\n')
					{
						AddToken(i, RegexToken.Categories.Comment);
						InsideInlineComment = false;
					}
				}
				else if (InsideComment)
				{
					if (Pattern[i] == ')')
					{
						AddToken(i, RegexToken.Categories.Comment);
						InsideComment = false;
					}
				}
				else
				{
					switch (Pattern[i])
					{
						case '\\':
							RegexHintPositions.Add(new KeyValuePair<int, HintType>(i, HintType.Character));

							if (i < Pattern.Length - 1)
							{
								i++;  // Since \ is an escape character, advance to the next character.

								if ("AZzGbB".IndexOf(Pattern[i]) >= 0) // assertions eg. \b
								{
									AddToken(i, RegexToken.Categories.Assertion);
								}
								if (@"wWdDsSrnftvae\".IndexOf(Pattern[i]) >= 0) // characters eg. \w
								{
									AddToken(i, RegexToken.Categories.Character);
								}
								else if (Pattern[i] != '0' && char.IsDigit(Pattern[i])) // backreferences eg. \1
								{
									int backreferenceMax = Math.Min((i + 2), Pattern.Length - 1);
									while (i < backreferenceMax)
									{
										if (char.IsDigit(Pattern[i + 1]))
										{
											i++;
										}
										else
											break;
									}
									AddToken(i, RegexToken.Categories.Backreference);
								}
								else if (Pattern[i] == 'k') // backreferences eg. \k<groupname>
								{
									int endBlockIndex = Pattern.IndexOf('>', i);
									if (endBlockIndex == -1) endBlockIndex = Pattern.Length - 1;
									if (endBlockIndex > i) i = endBlockIndex;
									AddToken(i, RegexToken.Categories.Backreference);
								}
								else // special characters
								{
									switch (Pattern[i])
									{
										case '0':
											int octalMax = Math.Min((i + 3), Pattern.Length - 1);
											while (i < octalMax)
											{
												if (char.IsDigit(Pattern[i + 1]))
												{
													i++;
												}
												else
													break;
											}
											AddToken(i, RegexToken.Categories.Character);
											break;

										case 'x':
											int hexMax = Math.Min((i + 2), Pattern.Length - 1);
											while (i < hexMax)
											{
												if (char.IsDigit(Pattern[i + 1]))
												{
													i++;
												}
												else
													break;
											}
											AddToken(i, RegexToken.Categories.Character);
											break;

										case 'c':
											int asciiMax = Math.Min((i + 4), Pattern.Length - 1);
											while (i < asciiMax)
											{
												if (char.IsDigit(Pattern[i + 1]))
												{
													i++;
												}
												else
													break;
											}
											AddToken(i, RegexToken.Categories.Character);
											break;

										case 'u':
											int unicodeMax = Math.Min((i + 4), Pattern.Length - 1);
											while (i < unicodeMax)
											{
												if (char.IsDigit(Pattern[i + 1]))
												{
													i++;
												}
												else
													break;
											}
											AddToken(i, RegexToken.Categories.Character);
											break;

										case 'p':
										case 'P':
											RegexHintPositions.Add(new KeyValuePair<int, HintType>(i + 1, HintType.NamedCharacterClass));

											int endBlockIndex = Pattern.IndexOf('}', i);
											if (endBlockIndex == -1) endBlockIndex = Pattern.Length - 1;
											if (endBlockIndex > i) i = endBlockIndex;
											AddToken(i, RegexToken.Categories.Character);
											break;

										default:
											if (char.IsLetter(Pattern[i]))
												AddToken(i, RegexToken.Categories.Invalid);
											else
												AddToken(i, RegexToken.Categories.Character);
											break;
									}

								}
							}
							break;

						case '(':
							if (BracketsCount == 0) // if not inside a character class, then it's a group or subexpression
							{
								RegexHintPositions.Add(new KeyValuePair<int, HintType>(i, HintType.Grouping));

								if (i < Pattern.Length - 2 && Pattern[i + 1] == '?')
								{
									if ("-imnsx".IndexOf(Pattern[i + 2]) >= 0) // toggle options
									{
										i += 2;

										bool EnableOption = true;
										while (i < Pattern.Length)
										{
											if (Pattern[i] == '-') EnableOption = false;
											else if (Pattern[i] == 'x') ignorePatternWhitespace = EnableOption;

											if (i < Pattern.Length - 1 && "-imnsx".IndexOf(Pattern[i + 1]) >= 0)
												i++;
											else
												break;
										}

										if (i < Pattern.Length - 1 && Pattern[i + 1] == ':')
										{
											i++;
										}
									}
									else
									{
										switch (Pattern[i + 2])
										{
											case ':':
												i += 2;
												break;
											case '=':
												i += 2;
												break;
											case '!':
												i += 2;
												break;
											case '#':
												i += 2;
												InsideComment = true;
												break;
											case '<':
												if (i + 3 < Pattern.Length)
												{
													switch (Pattern[i + 3])
													{
														case '=':
															i += 3;
															break;
														case '!':
															i += 3;
															break;
														default: // named group
															i += 3;
															while (i < Pattern.Length - 1 && (Char.IsLetterOrDigit(Pattern[i]) || Pattern[i] == '-'))
															{
																i++;
															}
															break;
													}
												}
												break;
											case '>':
												i += 2;
												break;
										}
									}
								}

								if (!InsideComment)
								{
									AddToken(i, RegexToken.Categories.Grouping);
									ParenthesesCount++;
								}
							}
							break;

						case ')':
							if (BracketsCount == 0)
							{
								ParenthesesCount--;
								AddToken(i, RegexToken.Categories.Grouping);
							}
							break;

						case '{':
							if (BracketsCount == 0)
							{
								RegexHintPositions.Add(new KeyValuePair<int, HintType>(i, HintType.Quantifier));

								bool IsQuantifier = false;
								int QuantifierIndex = i + 1;
								while (QuantifierIndex < Pattern.Length && char.IsDigit(Pattern[QuantifierIndex]))
								{
									QuantifierIndex++;
									IsQuantifier = true;
								}

								if (IsQuantifier && QuantifierIndex < Pattern.Length)
								{
									IsQuantifier = false;

									if (Pattern[QuantifierIndex] == ',' && QuantifierIndex < Pattern.Length - 1)
										QuantifierIndex++;

									while (QuantifierIndex < Pattern.Length)
									{
										if (Pattern[QuantifierIndex] == '}')
										{
											IsQuantifier = true;
											break;
										}
										else if (!char.IsDigit(Pattern[QuantifierIndex]))
										{
											break;
										}

										QuantifierIndex++;
									}

									if (IsQuantifier)
									{
										if (QuantifierIndex > i) i = QuantifierIndex;
										AddToken(i, RegexToken.Categories.Quantifier);
									}

								}
							}
							break;

						case '[':
							RegexHintPositions.Add(new KeyValuePair<int, HintType>(i, HintType.CharacterClass));

							BracketsCount++;
							break;

						case ']':
							if (BracketsCount > 0) BracketsCount--;
							if (BracketsCount == 0)
							{
								AddToken(i, RegexToken.Categories.Character);
							}
							break;

						case '.':
							if (BracketsCount == 0)
								AddToken(i, RegexToken.Categories.Character);
							break;

						case '^':
						case '$':
							if (BracketsCount == 0)
								AddToken(i, RegexToken.Categories.Assertion);
							break;

						case '|':
							if (BracketsCount == 0)
								AddToken(i, RegexToken.Categories.Alternation);
							break;

						case '+':
						case '*':
						case '?':
							if (BracketsCount == 0)
								AddToken(i, RegexToken.Categories.Quantifier);
							break;

						default:
							if (BracketsCount == 0 && i < Pattern.Length - 1)
							{
								if (ignorePatternWhitespace && Pattern[i] == '#')
								{
									InsideInlineComment = true;
								}
								else if (".(){}[]\\^$|+*?#".IndexOf(Pattern[i + 1]) >= 0) // if next character is a reserved character then add the pattern we have so far
								{
									AddToken(i);
								}
							}
							break;
					}
				}
			}

			// add any left over pattern that hasn't been tokenized yet
			if (Position < Pattern.Length)
			{
				if (InsideInlineComment)
					AddToken(Pattern.Length - 1, RegexToken.Categories.Comment);
				else
					AddToken(Pattern.Length - 1);
			}

			// check for unclosed brackets
			if (BracketsCount != 0 || ParenthesesCount != 0) IsValid = false;

			if (BracketsCount > 0)
			{
				for (int i = FlattenedTokens.Count - 1; i >= 0; i--)
				{
					bool IsEscaped = false;
					foreach (char c in FlattenedTokens[i].Pattern)
					{
						if (!IsEscaped)
						{
							if (c == '[') BracketsCount--;
							else if (c == ']') BracketsCount++;
							else if (c == '\\') IsEscaped = true;
						}
						else
						{
							IsEscaped = false;
						}
					}

					FlattenedTokens[i].Category = RegexToken.Categories.Invalid;

					if (BracketsCount <= 0) break;
				}
			}

			// check for unclosed parentheses
			if (ParenthesesCount > 0)
			{
				for (int i = FlattenedTokens.Count - 1; i >= 0; i--)
				{
					bool IsEscaped = false;
					foreach (char c in FlattenedTokens[i].Pattern)
					{
						if (!IsEscaped)
						{
							if (c == '(') ParenthesesCount--;
							else if (c == ')') ParenthesesCount++;
							else if (c == '\\') IsEscaped = true;
						}
						else
						{
							IsEscaped = false;
						}
					}

					FlattenedTokens[i].Category = RegexToken.Categories.Invalid;

					if (ParenthesesCount <= 0) break;
				}
			}
			else if (ParenthesesCount < 0)
			{
				for (int i = 0; i < FlattenedTokens.Count; i++)
				{
					bool IsEscaped = false;
					foreach (char c in FlattenedTokens[i].Pattern)
					{
						if (!IsEscaped)
						{
							if (c == '(') ParenthesesCount--;
							else if (c == ')') ParenthesesCount++;
							else if (c == '\\') IsEscaped = true;
						}
						else
						{
							IsEscaped = false;
						}
					}

					FlattenedTokens[i].Category = RegexToken.Categories.Invalid;

					if (ParenthesesCount >= 0) break;
				}
			}

		}
	}
}
